#include <stdio.h>
#include <stdlib.h>

// 二叉排序树
typedef struct bstnode
{
    int key;                // 关键字
    char other;             // 其他数据域
    struct bstnode *lchild; // 左子树指针
    struct bstnode *rchild; // 右子树指针
} BSTNode, *BSTree;

void inorder(BSTree tree);
void preorder(BSTree tree);
void postorder(BSTree tree);

// 二叉排序树插入元素
void insertBST(BSTree *BST, int key)
{
    // 二叉排序树为空，则新插入结点则作为根结点。否则必为叶子结点
    if ((*BST) == NULL)
    {
        (*BST) = (BSTNode *)malloc(sizeof(BSTNode));
        (*BST)->key = key;
        (*BST)->lchild = NULL;
        (*BST)->rchild = NULL;
    }
    else
    {
        printf("key==>%d\n", (*BST)->key);
        // 若插入元素小于 当前结点元素，则插入左子结点
        if (key < (*BST)->key)
        {
            insertBST(&((*BST)->lchild), key);
        }
        else
        {
            insertBST(&((*BST)->rchild), key);
        }
    }
}

BSTree buildBSTree(int array[], int len)
{
    BSTree root = NULL;
    for (int i = 0; i < len; i++){
        insertBST(&root, array[i]);
        // printf("i=%d, root is %d\n", i, &root->key);
    }
        
    return root;
}

BSTNode *searchBSTNode(BSTree BST, int key)
{
    if (BST == NULL)
        return NULL;

    if (key == BST->key)
        return BST;

    if (key < BST->key)
        return searchBSTNode(BST->lchild, key);

    return searchBSTNode(BST->rchild, key);
}

// 层次序列生成二叉树. BUG: 有问题，之后在看
BSTree createBST(char arr[], int len)
{
    BSTree root = (BSTNode *)malloc(sizeof(BSTNode));
    root->other = arr[0];
    root->lchild = NULL;
    root->rchild = NULL;

    BSTNode *node = root;
    BSTNode *subNode;

    for (int i = 1; i < len; i++)
    {
        subNode = (BSTNode *)malloc(sizeof(BSTNode));
        subNode->other = arr[i];
        subNode->lchild = NULL;
        subNode->rchild = NULL;

        if (i % 2 == 0)
        {
            node->lchild = subNode;
            node = node->lchild;
        }
        else
        {
            node->rchild = subNode;
            node = node->rchild;
        }
    }
    return root;
}

BSTree insertBSTree(BSTree BST, BSTNode *S)
{
    BSTNode *f, *p = BST;
    while (p)
    {
        f = p;
        if (S->key < p->key)
        {
            p = p->lchild;
        }
        else
        {
            p = p->rchild;
        }
    }

    if (BST == NULL)
    {
        BST = S;
    }
    else if (S->key < f->key)
    {
        f->lchild = S;
    }
    else
    {
        f->rchild = S;
    }
    return BST;
}

int main()
{
    // char arr[] = {'1', '2', '3', '4', '5', '6', '7'};
    // BSTree B = createBST(arr, 7);
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    BSTree B = buildBSTree(arr, 7);
    printf("\n前序遍历: ");
    preorder(B);
    printf("\n中序遍历: ");
    inorder(B);
    printf("\n后序遍历: ");
    postorder(B);
    printf("\n");
    BSTNode * findResult = searchBSTNode(B, 8);
    printf("\n查找结果: %c\n", findResult == NULL ? 'N':  findResult->key + '0');
    return 0;
}

// ------------------------------递归遍历--------------------------
/**
 * 中序遍历:
 */
void inorder(BSTree tree)
{
    if (tree == NULL)
        return;
    inorder(tree->lchild);
    printf("%d ", tree->key);
    inorder(tree->rchild);
}

/**
 * 前序遍历:
 */
void preorder(BSTree tree)
{
    if (tree == NULL)
        return;
    printf("%d ", tree->key);
    preorder(tree->lchild);
    preorder(tree->rchild);
}

/**
 * 后序遍历:
 */
void postorder(BSTree tree)
{
    if (tree == NULL)
        return;
    postorder(tree->lchild);
    postorder(tree->rchild);
    printf("%d ", tree->key);
}
